package SwordFingerOffer;

import java.util.Arrays;

public class Q39_ExceedHalf {
    //数组中超过一半的数组
    //词频就不要考虑了..


    public int majorityElement(int[] nums) {

        //排序 中间 O(NlogN)
//        Arrays.sort(nums);
//        return nums[nums.length / 2];

        //O(N)的解法有没有? ==> 词频 ==> 浪费空间
        // 摩尔投票 ==> 时间 O(n) 空间 O(1)
        int score = 1;
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == ans){
                score ++;
            }else {
                score --;
            }
            if (score == 0){
                //当前位不考虑，下一位为候选胜者
                ans = i + 1 != nums.length ? nums[i + 1] : ans;
            }
        }
        return ans;

    }
}
